package com.bee.剑指offer;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
 *
 * @Author yong.Mr
 * @data 2021-04-23
 * @version 1.0.0
 */
public class 二叉搜索树的后序遍历序列 {

    public static boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) {
            return Boolean.FALSE;
        }
        boolean result = judgeIsBST(sequence, 0, sequence.length - 1);
        return result;
    }

    public static boolean judgeIsBST(int[] sequence, int start, int end) {
        if (start >= end) {
            return Boolean.TRUE;
        }
        int temp = start;
        int pivot = 0;
        while (sequence[temp] < sequence[end]) {
            temp++;
        }
        pivot = temp;
        while (sequence[temp] > sequence[end]) {
            temp++;
        }
        if(temp < end) {
            return Boolean.FALSE;
        }
        return judgeIsBST(sequence,start,pivot - 1) && judgeIsBST(sequence, pivot, end - 1);
    }

    public static void main(String[] args) {
        boolean b = VerifySquenceOfBST(new int[]{7,4,6,5});
        System.out.println(b);
    }
}
